﻿/*
菲波那契数的余数 
Time Limit:1000MS  Memory Limit:32768K


Description:
菲波那契数大家可能都已经很熟悉了： f(1)=0 f(2)=1 f(n)=f(n-1)+f(n-2) n>2 
因此，当需要其除以某个数的余数时，不妨加一些处理就可以得到。 

Input:
输入数据为一些整数对P、K，P(1<P<5000)表示菲波那契数的序号，K(1<=K<15)表示2的幂次方。遇到两个空格隔开的0时表示结束处理。 
Output:
输出其第P个菲波那契数除以2的K次方的余数。 
Sample Input:
6 2
20 10
0 0
Sample Output:
1
85
*/
#include <stdio.h>
int main(int argc, char* argv[])
{
	unsigned p, k;
	
	while(EOF!=scanf("%u%u", &p, &k) && p &&k)
	{
		unsigned and=~(~0<<k);
		unsigned f1=0, f2=1;
		if(p<2)
		{
			printf("1\n");
			continue;
		}

		p-=2;
		while(p--)
		{
			unsigned tmp=f2;
			f2=(f2+f1)&and;
			f1=tmp;
		}
		printf("%u\n", f2);
	}
	return 0;
}